public class 二叉树的序列化与反序列化 {



    //序列化
    //先创建一个全局变量来存储一下先序遍历的字符串
    public static StringBuilder sb;
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        sb = new StringBuilder();
        //进行先序遍历
        dfs(root);
        //将字符串返回
        return sb.toString();
    }
    public void dfs(TreeNode root){
        if(root == null){
            sb.append("#,");
            return;
        }
        sb.append(root.val + ",");
        dfs(root.left);
        dfs(root.right);
    }


    //反序列化
    public static String[] datas;
    public static int cnt;
    public TreeNode deserialize(String data) {
        //先将data进行分割, 用cnt来标记每一个数值
        datas = data.split(",");
        cnt = 0;
        return dfs1();
    }
    public TreeNode dfs1(){
        //提取一下该数
        String str = datas[cnt++];
        //如果该位置为空, 直接返回
        if(str.equals("#")){
            return null;
        }
        //如果不为空, 先创建这个节点
        TreeNode cur = new TreeNode(Integer.parseInt(str));
        //左边遍历连接一下, 右边连接一下
        cur.left = dfs1();
        cur.right = dfs1();
        return cur;
    }


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        // 无参构造函数
        TreeNode() {}

        // 只带一个值的构造函数
        TreeNode(int val) {
            this.val = val;
        }

        // 带值、左子节点和右子节点的构造函数
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
